package com.ctrip.study.algorithm.pratice;

import org.junit.Test;

import junit.framework.TestCase;

/**
  	在二元树中找出和为某一值的所有路径
  	题目：输入一个整数和一棵二元树。
	从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
	打印出和与输入整数相等的所有路径。
	例如输入整数22 和如下二元树
	10
	/ \
	5 12
	/ \
	4 7
	则打印出两条路径：10, 12 和10, 5, 7。
 */
public class TreeSumRoute extends TestCase{
	
	
	@Test
	public void test(){
		Tree tree = buildTree();
		sumRoute(tree, 22);
	}
	
	
	public void sumRoute(Tree tree, int sum){
		if(tree == null || tree.root == null){
			return;
		}
		printRoute(tree.root, sum, "");
	}
	
	
	private void printRoute(TreeNode node, int sum, String route) {
		if(node == null || node.data > sum){
			return;
		}
		sum -= node.data;
		route += node + "--->";
		if(sum == 0){
			System.out.println(route.substring(0, route.length() - 4));
		}else{
			printRoute(node.left, sum, route);
			printRoute(node.right, sum, route);
		}
	}


	public Tree buildTree(){
		Tree tree = new Tree();
		tree.insert(10);
		tree.insert(5);
		tree.insert(12);
		tree.insert(4);
		tree.insert(7);
		return tree;
	}
	
	
	public class TreeNode {
		public int data;
		public TreeNode left;
		public TreeNode right;
		
		public TreeNode(int data){
			this.data = data;
		}
		
		public Boolean isLeaf(){
			return (left == null && right == null);
		}
		
		@Override
		public String toString() {
			return "TreeNode [data=" + data + "]";
		}
		
	}
	
	public class Tree {
		public TreeNode root;
		
		public void insert(int data){
			if(root == null){
				root = new TreeNode(data);
			}else{
				TreeNode currNode = root;
				TreeNode parentNode = null;
				boolean isLeft = true;
				while(currNode != null){
					parentNode = currNode;
					if(data < currNode.data){
						currNode = currNode.left;
						isLeft = true;
					}else{
						currNode = currNode.right;
						isLeft = false;
					}
				}
				if(isLeft){
					parentNode.left = new TreeNode(data);
				}else{
					parentNode.right = new TreeNode(data);
				}
			}
		}
	}

}











